//https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=13&tqId=1375406&ru=%2Fpractice%2F72a5a919508a4251859fb2cfb987a0e6&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思想：递归实现，复杂度高，这是多个题目的实现思路，当前有多种选择时，怎么进行选择；
//动态规划：

#include <iostream>
#include <string>
#include <cstddef>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        bool match_res = false;
        if (str.empty()|| pattern.empty()) return match_res;
        match_res = match_core(str, 0, pattern, 0);
        return match_res;
    }
    bool match_core(string s1,size_t i1,string s2,size_t i2) {
        if (s1.length() == i1  && i2 == s2.length()) {
            return true;
        }
        if (i1 < s1.length() && i2 == s2.length()) {
            return false;
        }
        if (i1 ==s1.length() && i2 < s2.length()) {
            if (i2+1 <s2.length() && s2[i2+1] == '*') {
                return match_core(s1, i1, s2, i2 + 2);
            }else  {
                return false;
            }
        }
        if (i2+1 <s2.length() && s2[i2+1] == '*' ) {
            if (s1[i1] == s2[i2]||(s2[i2] == '.' )) {
                return match_core(s1,i1+1,s2,i2+2)||match_core(s1,i1+1, s2,i2)||match_core(s1,i1, s2,i2+2);
            } else {
               return match_core(s1,i1,s2,i2+2);
            }
        }

        if (s1[i1] == s2[i2] || s2[i2] == '.') {
            return match_core(s1, i1+1, s2, i2+1);
        }   
        return false;     
    }
};